<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <link rel="stylesheet" href="../../aosa.css" type="text/css">
    <title>500 Lines or Less: A Simple Object Model</title>
  </head>
  <body>

    <div class="titlebox">
      <h1>500 Lines or Less<br>A Simple Object Model</h1>
      <p class="author">Carl Friedrich Bolz</p>
    </div>

    <p><em>Carl Friedrich Bolz is a researcher at King's College London and is broadly interested in the implementation and optimization of all kinds of dynamic languages. He is one of the core authors of PyPy/RPython and has worked on implementations of Prolog, Racket, Smalltalk, PHP and Ruby. He's <a href="https://twitter.com/cfbolz">@cfbolz</a> on Twitter.</em></p>

<h2 id="introduction">Introduction</h2>

<p>Object-oriented programming is one of the major programming paradigms in use today, with a lot of languages providing some form of object-orientation. While on the surface the mechanisms that different object-oriented programming languages provide to the programmer are very similar, the details can vary a lot. Commonalities of most languages are the presence of objects and some kind of inheritance mechanism. Classes, however, are a feature that not every language supports directly. For example, in prototype-based languages like Self or JavaScript, the concept of class does not exist and objects instead inherit directly from each other.</p>

<p>Understanding the differences between different object models can be interesting. They often reveal the family resemblance between different languages. It can be useful to put the model of a new language into the context of the models of other languages, both to quickly understand the new model, and to get a better feeling for the programming language design space.</p>

<p>This chapter explores the implementation of a series of very simple object models. It starts out with simple instances and classes, and the ability to call methods on instances. This is the &quot;classical&quot; object-oriented approach that was established in early OO languages such as Simula 67 and Smalltalk. This model is then extended step by step, the next two steps exploring different language design choices, and the last step improving the efficiency of the object model. The final model is not that of a real language, but an idealized, simplified version of Python's object model.</p>

<p>The object models presented in this chapter will be implemented in Python. The code works on both Python 2.7 and 3.4. To understand the behaviour and the design choices better, the chapter will also present tests for the object model. The tests can be run with either py.test or nose.</p>

<p>The choice of Python as an implementation language is quite unrealistic. A &quot;real&quot; VM is typically implemented in a low-level language like C/C++ and needs a lot of attention to engineering detail to make it efficient. However, the simpler implementation language makes it easier to focus on actual behaviour differences instead of getting bogged down by implementation details.</p>

<h2 id="method-based-model">Method-Based Model</h2>

<p>The object model we will start out with is an extremely simplified version of that of Smalltalk. Smalltalk was an object-oriented programming language designed by Alan Kay's group at Xerox PARC in the 1970s. It popularized object-oriented programming, and is the source of many features found in today's programming languages. One of the core tenets of Smalltalk's language design was &quot;everything is an object&quot;. Smalltalk's most immediate successor in use today is Ruby, which uses a more C-like syntax but retains most of Smalltalk's object model.</p>

<p>The object model in this section will have classes and instances of them, the ability to read and write attributes into objects, the ability to call methods on objects, and the ability for a class to be a subclass of another class. Right from the beginning, classes will be completely ordinary objects that can themselves have attributes and methods.</p>

<p>A note on terminology: In this chapter I will use the word &quot;instance&quot; to mean -&quot;an object that is not a class&quot;.</p>

<p>A good approach to start with is to write a test to specify what the to-be-implemented behaviour should be. All tests presented in this chapter will consist of two parts. First, a bit of regular Python code defining and using a few classes, and making use of increasingly advanced features of the Python object model. Second, the corresponding test using the object model we will implement in this chapter, instead of normal Python classes.</p>

<p>The mapping between using normal Python classes and using our object model will be done manually in the tests. For example, instead of writing <code>obj.attribute</code> in Python, in the object model we would use a method <code>obj.read_attr(&quot;attribute&quot;)</code>. This mapping would, in a real language implementation, be done by the interpreter of the language, or a compiler.</p>

<p>A further simplification in this chapter is that we make no sharp distinction between the code that implements the object model and the code that is used to write the methods used in the objects. In a real system, the two would often be implemented in different programming languages.</p>

<p>Let us start with a simple test for reading and writing object fields.</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_read_write_field():
    <span class="co"># Python code</span>
    <span class="kw">class</span> A(<span class="dt">object</span>):
        <span class="kw">pass</span>
    obj = A()
    obj.a = <span class="dv">1</span>
    <span class="kw">assert</span> obj.a == <span class="dv">1</span>

    obj.b = <span class="dv">5</span>
    <span class="kw">assert</span> obj.a == <span class="dv">1</span>
    <span class="kw">assert</span> obj.b == <span class="dv">5</span>

    obj.a = <span class="dv">2</span>
    <span class="kw">assert</span> obj.a == <span class="dv">2</span>
    <span class="kw">assert</span> obj.b == <span class="dv">5</span>

    <span class="co"># Object model code</span>
    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT, fields={}, metaclass=TYPE)
    obj = Instance(A)
    obj.write_attr(<span class="st">&quot;a&quot;</span>, <span class="dv">1</span>)
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;a&quot;</span>) == <span class="dv">1</span>

    obj.write_attr(<span class="st">&quot;b&quot;</span>, <span class="dv">5</span>)
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;a&quot;</span>) == <span class="dv">1</span>
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;b&quot;</span>) == <span class="dv">5</span>

    obj.write_attr(<span class="st">&quot;a&quot;</span>, <span class="dv">2</span>)
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;a&quot;</span>) == <span class="dv">2</span>
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;b&quot;</span>) == <span class="dv">5</span></code></pre>

<p>The test uses three things that we have to implement. The classes <code>Class</code> and <code>Instance</code> represent classes and instances of our object model, respectively. There are two special instances of class: <code>OBJECT</code> and <code>TYPE</code>. <code>OBJECT</code> corresponds to <code>object</code> in Python and is the ultimate base class of the inheritance hierarchy. <code>TYPE</code> corresponds to <code>type</code> in Python and is the type of all classes.</p>

<p>To do anything with instances of <code>Class</code> and <code>Instance</code>, they implement a shared interface by inheriting from a shared base class <code>Base</code> that exposes a number of methods:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Base(<span class="dt">object</span>):
    <span class="co">&quot;&quot;&quot; The base class that all of the object model classes inherit from. &quot;&quot;&quot;</span>

    <span class="kw">def</span> <span class="ot">__init__</span>(<span class="ot">self</span>, cls, fields):
        <span class="co">&quot;&quot;&quot; Every object has a class. &quot;&quot;&quot;</span>
        <span class="ot">self</span>.cls = cls
        <span class="ot">self</span>._fields = fields

    <span class="kw">def</span> read_attr(<span class="ot">self</span>, fieldname):
        <span class="co">&quot;&quot;&quot; read field &#39;fieldname&#39; out of the object &quot;&quot;&quot;</span>
        <span class="kw">return</span> <span class="ot">self</span>._read_dict(fieldname)

    <span class="kw">def</span> write_attr(<span class="ot">self</span>, fieldname, value):
        <span class="co">&quot;&quot;&quot; write field &#39;fieldname&#39; into the object &quot;&quot;&quot;</span>
        <span class="ot">self</span>._write_dict(fieldname, value)

    <span class="kw">def</span> <span class="dt">isinstance</span>(<span class="ot">self</span>, cls):
        <span class="co">&quot;&quot;&quot; return True if the object is an instance of class cls &quot;&quot;&quot;</span>
        <span class="kw">return</span> <span class="ot">self</span>.cls.<span class="dt">issubclass</span>(cls)

    <span class="kw">def</span> callmethod(<span class="ot">self</span>, methname, *args):
        <span class="co">&quot;&quot;&quot; call method &#39;methname&#39; with arguments &#39;args&#39; on object &quot;&quot;&quot;</span>
        meth = <span class="ot">self</span>.cls._read_from_class(methname)
        <span class="kw">return</span> meth(<span class="ot">self</span>, *args)

    <span class="kw">def</span> _read_dict(<span class="ot">self</span>, fieldname):
        <span class="co">&quot;&quot;&quot; read an field &#39;fieldname&#39; out of the object&#39;s dict &quot;&quot;&quot;</span>
        <span class="kw">return</span> <span class="ot">self</span>._fields.get(fieldname, MISSING)

    <span class="kw">def</span> _write_dict(<span class="ot">self</span>, fieldname, value):
        <span class="co">&quot;&quot;&quot; write a field &#39;fieldname&#39; into the object&#39;s dict &quot;&quot;&quot;</span>
        <span class="ot">self</span>._fields[fieldname] = value

MISSING = <span class="dt">object</span>()</code></pre>

<p>The <code>Base</code> class implements storing the class of an object, and a dictionary containing the field values of the object. Now we need to implement <code>Class</code> and <code>Instance</code>. The constructor of <code>Instance</code> takes the class to be instantiated and initializes the <code>fields</code> <code>dict</code> as an empty dictionary. Otherwise <code>Instance</code> is just a very thin subclass around <code>Base</code> that does not add any extra functionality.</p>

<p>The constructor of <code>Class</code> takes the name of the class, the base class, the dictionary of the class and the metaclass. For classes, the fields are passed into the constructor by the user of the object model. The class constructor also takes a base class, which the tests so far don't need but which we will make use of in the next section.</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Instance(Base):
    <span class="co">&quot;&quot;&quot;Instance of a user-defined class. &quot;&quot;&quot;</span>

    <span class="kw">def</span> <span class="ot">__init__</span>(<span class="ot">self</span>, cls):
        <span class="kw">assert</span> <span class="dt">isinstance</span>(cls, Class)
        Base.<span class="ot">__init__</span>(<span class="ot">self</span>, cls, {})


<span class="kw">class</span> Class(Base):
    <span class="co">&quot;&quot;&quot; A User-defined class. &quot;&quot;&quot;</span>

    <span class="kw">def</span> <span class="ot">__init__</span>(<span class="ot">self</span>, name, base_class, fields, metaclass):
        Base.<span class="ot">__init__</span>(<span class="ot">self</span>, metaclass, fields)
        <span class="ot">self</span>.name = name
        <span class="ot">self</span>.base_class = base_class</code></pre>

<p>Since classes are also a kind of object, they (indirectly) inherit from <code>Base</code>. Thus, the class needs to be an instance of another class: its metaclass.</p>

<p>Now our first test almost passes. The only missing bit is the definition of the base classes <code>TYPE</code> and <code>OBJECT</code>, which are both instances of <code>Class</code>. For these we will make a major departure from the Smalltalk model, which has a fairly complex metaclass system. Instead we will use the model introduced in ObjVlisp<a href="#fn1" class="footnoteRef" id="fnref1"><sup>1</sup></a>, which Python adopted.</p>

<p>In the ObjVlisp model, <code>OBJECT</code> and <code>TYPE</code> are intertwined. <code>OBJECT</code> is the base class of all classes, meaning it has no base class. <code>TYPE</code> is a subclass of <code>OBJECT</code>. By default, every class is an instance of <code>TYPE</code>. In particular, both <code>TYPE</code> and <code>OBJECT</code> are instances of <code>TYPE</code>. However, the programmer can also subclass <code>TYPE</code> to make a new metaclass:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="co"># set up the base hierarchy as in Python (the ObjVLisp model)</span>
<span class="co"># the ultimate base class is OBJECT</span>
OBJECT = Class(name=<span class="st">&quot;object&quot;</span>, base_class=<span class="ot">None</span>, fields={}, metaclass=<span class="ot">None</span>)
<span class="co"># TYPE is a subclass of OBJECT</span>
TYPE = Class(name=<span class="st">&quot;type&quot;</span>, base_class=OBJECT, fields={}, metaclass=<span class="ot">None</span>)
<span class="co"># TYPE is an instance of itself</span>
TYPE.cls = TYPE
<span class="co"># OBJECT is an instance of TYPE</span>
OBJECT.cls = TYPE</code></pre>

<p>To define new metaclasses, it is enough to subclass <code>TYPE</code>. However, in the rest of this chapter we won't do that; we'll simply always use <code>TYPE</code> as the metaclass of every class.</p>

<div class="center figure">
<a name="figure-14.1"></a><img src="objmodel-images/inheritance.png" alt="Figure 14.1 - Inheritance" title="Figure 14.1 - Inheritance" />
</div>

<p class="center figcaption">
<small>Figure 14.1 - Inheritance</small>
</p>

<p>Now the first test passes. The second test checks that reading and writing attributes works on classes as well. It's easy to write, and passes immediately. </p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_read_write_field_class():
    <span class="co"># classes are objects too</span>
    <span class="co"># Python code</span>
    <span class="kw">class</span> A(<span class="dt">object</span>):
        <span class="kw">pass</span>
    A.a = <span class="dv">1</span>
    <span class="kw">assert</span> A.a == <span class="dv">1</span>
    A.a = <span class="dv">6</span>
    <span class="kw">assert</span> A.a == <span class="dv">6</span>

    <span class="co"># Object model code</span>
    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT, fields={<span class="st">&quot;a&quot;</span>: <span class="dv">1</span>}, metaclass=TYPE)
    <span class="kw">assert</span> A.read_attr(<span class="st">&quot;a&quot;</span>) == <span class="dv">1</span>
    A.write_attr(<span class="st">&quot;a&quot;</span>, <span class="dv">5</span>)
    <span class="kw">assert</span> A.read_attr(<span class="st">&quot;a&quot;</span>) == <span class="dv">5</span></code></pre>

<h3 id="isinstance-checking"><code>isinstance</code> Checking</h3>

<p>So far we haven't taken advantage of the fact that objects have classes. The next test implements the <code>isinstance</code> machinery:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_isinstance():
    <span class="co"># Python code</span>
    <span class="kw">class</span> A(<span class="dt">object</span>):
        <span class="kw">pass</span>
    <span class="kw">class</span> B(A):
        <span class="kw">pass</span>
    b = B()
    <span class="kw">assert</span> <span class="dt">isinstance</span>(b, B)
    <span class="kw">assert</span> <span class="dt">isinstance</span>(b, A)
    <span class="kw">assert</span> <span class="dt">isinstance</span>(b, <span class="dt">object</span>)
    <span class="kw">assert</span> not <span class="dt">isinstance</span>(b, <span class="dt">type</span>)

    <span class="co"># Object model code</span>
    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT, fields={}, metaclass=TYPE)
    B = Class(name=<span class="st">&quot;B&quot;</span>, base_class=A, fields={}, metaclass=TYPE)
    b = Instance(B)
    <span class="kw">assert</span> b.<span class="dt">isinstance</span>(B)
    <span class="kw">assert</span> b.<span class="dt">isinstance</span>(A)
    <span class="kw">assert</span> b.<span class="dt">isinstance</span>(OBJECT)
    <span class="kw">assert</span> not b.<span class="dt">isinstance</span>(TYPE)</code></pre>

<p>To check whether an object <code>obj</code> is an instance of a certain class <code>cls</code>, it is enough to check whether <code>cls</code> is a superclass of the class of <code>obj</code>, or the class itself. To check whether a class is a superclass of another class, the chain of superclasses of that class is walked. If and only if the other class is found in that chain, it is a superclass. The chain of superclasses of a class, including the class itself, is called the &quot;method resolution order&quot; of that class. It can easily be computed recursively:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Class(Base):
    ...

    <span class="kw">def</span> method_resolution_order(<span class="ot">self</span>):
        <span class="co">&quot;&quot;&quot; compute the method resolution order of the class &quot;&quot;&quot;</span>
        <span class="kw">if</span> <span class="ot">self</span>.base_class is <span class="ot">None</span>:
            <span class="kw">return</span> [<span class="ot">self</span>]
        <span class="kw">else</span>:
            <span class="kw">return</span> [<span class="ot">self</span>] + <span class="ot">self</span>.base_class.method_resolution_order()

    <span class="kw">def</span> <span class="dt">issubclass</span>(<span class="ot">self</span>, cls):
        <span class="co">&quot;&quot;&quot; is self a subclass of cls? &quot;&quot;&quot;</span>
        <span class="kw">return</span> cls in <span class="ot">self</span>.method_resolution_order()</code></pre>

<p>With that code, the test passes.</p>

<h3 id="calling-methods">Calling Methods</h3>

<p>The remaining missing feature for this first version of the object model is the ability to call methods on objects. In this chapter we will implement a simple single inheritance model.</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_callmethod_simple():
    <span class="co"># Python code</span>
    <span class="kw">class</span> A(<span class="dt">object</span>):
        <span class="kw">def</span> f(<span class="ot">self</span>):
            <span class="kw">return</span> <span class="ot">self</span>.x + <span class="dv">1</span>
    obj = A()
    obj.x = <span class="dv">1</span>
    <span class="kw">assert</span> obj.f() == <span class="dv">2</span>

    <span class="kw">class</span> B(A):
        <span class="kw">pass</span>
    obj = B()
    obj.x = <span class="dv">1</span>
    <span class="kw">assert</span> obj.f() == <span class="dv">2</span> <span class="co"># works on subclass too</span>

    <span class="co"># Object model code</span>
    <span class="kw">def</span> f_A(<span class="ot">self</span>):
        <span class="kw">return</span> <span class="ot">self</span>.read_attr(<span class="st">&quot;x&quot;</span>) + <span class="dv">1</span>
    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT, fields={<span class="st">&quot;f&quot;</span>: f_A}, metaclass=TYPE)
    obj = Instance(A)
    obj.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">1</span>)
    <span class="kw">assert</span> obj.callmethod(<span class="st">&quot;f&quot;</span>) == <span class="dv">2</span>

    B = Class(name=<span class="st">&quot;B&quot;</span>, base_class=A, fields={}, metaclass=TYPE)
    obj = Instance(B)
    obj.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">2</span>)
    <span class="kw">assert</span> obj.callmethod(<span class="st">&quot;f&quot;</span>) == <span class="dv">3</span></code></pre>

<p>To find the correct implementation of a method that is sent to an object, we walk the method resolution order of the class of the object. The first method found in the dictionary of one of the classes in the method resolution order is called:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Class(Base):
    ...

    <span class="kw">def</span> _read_from_class(<span class="ot">self</span>, methname):
        <span class="kw">for</span> cls in <span class="ot">self</span>.method_resolution_order():
            <span class="kw">if</span> methname in cls._fields:
                <span class="kw">return</span> cls._fields[methname]
        <span class="kw">return</span> MISSING</code></pre>

<p>Together with the code for <code>callmethod</code> in the <code>Base</code> implementation, this passes the test.</p>

<p>To make sure that methods with arguments work as well, and that overriding of methods is implemented correctly, we can use the following slightly more complex test, which already passes:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_callmethod_subclassing_and_arguments():
    <span class="co"># Python code</span>
    <span class="kw">class</span> A(<span class="dt">object</span>):
        <span class="kw">def</span> g(<span class="ot">self</span>, arg):
            <span class="kw">return</span> <span class="ot">self</span>.x + arg
    obj = A()
    obj.x = <span class="dv">1</span>
    <span class="kw">assert</span> obj.g(<span class="dv">4</span>) == <span class="dv">5</span>

    <span class="kw">class</span> B(A):
        <span class="kw">def</span> g(<span class="ot">self</span>, arg):
            <span class="kw">return</span> <span class="ot">self</span>.x + arg * <span class="dv">2</span>
    obj = B()
    obj.x = <span class="dv">4</span>
    <span class="kw">assert</span> obj.g(<span class="dv">4</span>) == <span class="dv">12</span>

    <span class="co"># Object model code</span>
    <span class="kw">def</span> g_A(<span class="ot">self</span>, arg):
        <span class="kw">return</span> <span class="ot">self</span>.read_attr(<span class="st">&quot;x&quot;</span>) + arg
    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT, fields={<span class="st">&quot;g&quot;</span>: g_A}, metaclass=TYPE)
    obj = Instance(A)
    obj.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">1</span>)
    <span class="kw">assert</span> obj.callmethod(<span class="st">&quot;g&quot;</span>, <span class="dv">4</span>) == <span class="dv">5</span>

    <span class="kw">def</span> g_B(<span class="ot">self</span>, arg):
        <span class="kw">return</span> <span class="ot">self</span>.read_attr(<span class="st">&quot;x&quot;</span>) + arg * <span class="dv">2</span>
    B = Class(name=<span class="st">&quot;B&quot;</span>, base_class=A, fields={<span class="st">&quot;g&quot;</span>: g_B}, metaclass=TYPE)
    obj = Instance(B)
    obj.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">4</span>)
    <span class="kw">assert</span> obj.callmethod(<span class="st">&quot;g&quot;</span>, <span class="dv">4</span>) == <span class="dv">12</span></code></pre>

<h2 id="attribute-based-model">Attribute-Based Model</h2>

<p>Now that the simplest version of our object model is working, we can think of ways to change it. This section will introduce the distinction between a method-based model and an attribute-based model. This is one of the core differences between Smalltalk, Ruby, and JavaScript on the one hand and Python and Lua on the other hand.</p>

<p>The method-based model has the method-calling as the primitive of program execution:</p>

<pre class="sourceCode python"><code class="sourceCode python">result = obj.f(arg1, arg2)</code></pre>

<p>The attribute-based model splits up method calling into two steps: looking up an attribute and calling the result:</p>

<pre class="sourceCode python"><code class="sourceCode python">method = obj.f
result = method(arg1, arg2)</code></pre>

<p>This difference can be shown in the following test:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_bound_method():
    <span class="co"># Python code</span>
    <span class="kw">class</span> A(<span class="dt">object</span>):
        <span class="kw">def</span> f(<span class="ot">self</span>, a):
            <span class="kw">return</span> <span class="ot">self</span>.x + a + <span class="dv">1</span>
    obj = A()
    obj.x = <span class="dv">2</span>
    m = obj.f
    <span class="kw">assert</span> m(<span class="dv">4</span>) == <span class="dv">7</span>

    <span class="kw">class</span> B(A):
        <span class="kw">pass</span>
    obj = B()
    obj.x = <span class="dv">1</span>
    m = obj.f
    <span class="kw">assert</span> m(<span class="dv">10</span>) == <span class="dv">12</span> <span class="co"># works on subclass too</span>

    <span class="co"># Object model code</span>
    <span class="kw">def</span> f_A(<span class="ot">self</span>, a):
        <span class="kw">return</span> <span class="ot">self</span>.read_attr(<span class="st">&quot;x&quot;</span>) + a + <span class="dv">1</span>
    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT, fields={<span class="st">&quot;f&quot;</span>: f_A}, metaclass=TYPE)
    obj = Instance(A)
    obj.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">2</span>)
    m = obj.read_attr(<span class="st">&quot;f&quot;</span>)
    <span class="kw">assert</span> m(<span class="dv">4</span>) == <span class="dv">7</span>

    B = Class(name=<span class="st">&quot;B&quot;</span>, base_class=A, fields={}, metaclass=TYPE)
    obj = Instance(B)
    obj.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">1</span>)
    m = obj.read_attr(<span class="st">&quot;f&quot;</span>)
    <span class="kw">assert</span> m(<span class="dv">10</span>) == <span class="dv">12</span></code></pre>

<p>While the setup is the same as the corresponding test for method calls, the way that the methods are called is different. First, the attribute with the name of the method is looked up on the object. The result of that lookup operation is a <em>bound method</em>, an object that encapsulates both the object as well as the function found in the class. Next, that bound method is called with a call operation<a href="#fn2" class="footnoteRef" id="fnref2"><sup>2</sup></a>.</p>

<p>To implement this behaviour, we need to change the <code>Base.read_attr</code> implementation. If the attribute is not found in the dictionary, it is looked for in the class. If it is found in the class, and the attribute is a callable, it needs to be turned into a bound method. To emulate a bound method we simply use a closure. In addition to changing <code>Base.read_attr</code> we can also change <code>Base.callmethod</code> to use the new approach to calling methods to make sure all the tests still pass.</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Base(<span class="dt">object</span>):
    ...
    <span class="kw">def</span> read_attr(<span class="ot">self</span>, fieldname):
        <span class="co">&quot;&quot;&quot; read field &#39;fieldname&#39; out of the object &quot;&quot;&quot;</span>
        result = <span class="ot">self</span>._read_dict(fieldname)
        <span class="kw">if</span> result is not MISSING:
            <span class="kw">return</span> result
        result = <span class="ot">self</span>.cls._read_from_class(fieldname)
        <span class="kw">if</span> _is_bindable(result):
            <span class="kw">return</span> _make_boundmethod(result, <span class="ot">self</span>)
        <span class="kw">if</span> result is not MISSING:
            <span class="kw">return</span> result
        <span class="kw">raise</span> <span class="ot">AttributeError</span>(fieldname)

    <span class="kw">def</span> callmethod(<span class="ot">self</span>, methname, *args):
        <span class="co">&quot;&quot;&quot; call method &#39;methname&#39; with arguments &#39;args&#39; on object &quot;&quot;&quot;</span>
        meth = <span class="ot">self</span>.read_attr(methname)
        <span class="kw">return</span> meth(*args)

<span class="kw">def</span> _is_bindable(meth):
    <span class="kw">return</span> <span class="dt">callable</span>(meth)

<span class="kw">def</span> _make_boundmethod(meth, <span class="ot">self</span>):
    <span class="kw">def</span> bound(*args):
        <span class="kw">return</span> meth(<span class="ot">self</span>, *args)
    <span class="kw">return</span> bound</code></pre>

<p>The rest of the code does not need to be changed at all.</p>

<h2 id="meta-object-protocols">Meta-Object Protocols</h2>

<p>In addition to &quot;normal&quot; methods that are called directly by the program, many dynamic languages support <em>special methods</em>. These are methods that aren't meant to be called directly but will be called by the object system. In Python those special methods usually have names that start and end with two underscores; e.g., <code>__init__</code>. Special methods can be used to override primitive operations and provide custom behaviour for them instead. Thus, they are hooks that tell the object model machinery exactly how to do certain things. Python's object model has <a href="https://docs.python.org/2/reference/datamodel.html#special-method-names">dozens of special methods</a>.</p>

<p>Meta-object protocols were introduced by Smalltalk, but were used even more by the object systems for Common Lisp, such as CLOS. That is also where the name <em>meta-object protocol</em>, for collections of special methods, was coined<a href="#fn3" class="footnoteRef" id="fnref3"><sup>3</sup></a>.</p>

<p>In this chapter we will add three such meta-hooks to our object model. They are used to fine-tune what exactly happens when reading and writing attributes. The special methods we will add first are <code>__getattr__</code> and <code>__setattr__</code>, which closely follow the behaviour of Python's namesakes.</p>

<h3 id="customizing-reading-and-writing-and-attribute">Customizing Reading and Writing and Attribute</h3>

<p>The method <code>__getattr__</code> is called by the object model when the attribute that is being looked up is not found by normal means; i.e., neither on the instance nor on the class. It gets the name of the attribute being looked up as an argument. An equivalent of the <code>__getattr__</code> special method was part of early Smalltalk<a href="#fn4" class="footnoteRef" id="fnref4"><sup>4</sup></a> systems under the name <code>doesNotUnderstand:</code>.</p>

<p>The case of <code>__setattr__</code> is a bit different. Since setting an attribute always creates it, <code>__setattr__</code> is always called when setting an attribute. To make sure that a <code>__setattr__</code> method always exists, the <code>OBJECT</code> class has a definition of <code>__setattr__</code>. This base implementation simply does what setting an attribute did so far, which is write the attribute into the object's dictionary. This also makes it possible for a user-defined <code>__setattr__</code> to delegate to the base <code>OBJECT.__setattr__</code> in some cases.</p>

<p>A test for these two special methods is the following:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_getattr():
    <span class="co"># Python code</span>
    <span class="kw">class</span> A(<span class="dt">object</span>):
        <span class="kw">def</span> <span class="ot">__getattr__</span>(<span class="ot">self</span>, name):
            <span class="kw">if</span> name == <span class="st">&quot;fahrenheit&quot;</span>:
                <span class="kw">return</span> <span class="ot">self</span>.celsius * <span class="dv">9</span>. / <span class="dv">5</span>. + <span class="dv">32</span>
            <span class="kw">raise</span> <span class="ot">AttributeError</span>(name)

        <span class="kw">def</span> <span class="ot">__setattr__</span>(<span class="ot">self</span>, name, value):
            <span class="kw">if</span> name == <span class="st">&quot;fahrenheit&quot;</span>:
                <span class="ot">self</span>.celsius = (value - <span class="dv">32</span>) * <span class="dv">5</span>. / <span class="dv">9</span>.
            <span class="kw">else</span>:
                <span class="co"># call the base implementation</span>
                <span class="dt">object</span>.<span class="ot">__setattr__</span>(<span class="ot">self</span>, name, value)
    obj = A()
    obj.celsius = <span class="dv">30</span>
    <span class="kw">assert</span> obj.fahrenheit == <span class="dv">86</span> <span class="co"># test __getattr__</span>
    obj.celsius = <span class="dv">40</span>
    <span class="kw">assert</span> obj.fahrenheit == <span class="dv">104</span>

    obj.fahrenheit = <span class="dv">86</span> <span class="co"># test __setattr__</span>
    <span class="kw">assert</span> obj.celsius == <span class="dv">30</span>
    <span class="kw">assert</span> obj.fahrenheit == <span class="dv">86</span>

    <span class="co"># Object model code</span>
    <span class="kw">def</span> <span class="ot">__getattr__</span>(<span class="ot">self</span>, name):
        <span class="kw">if</span> name == <span class="st">&quot;fahrenheit&quot;</span>:
            <span class="kw">return</span> <span class="ot">self</span>.read_attr(<span class="st">&quot;celsius&quot;</span>) * <span class="dv">9</span>. / <span class="dv">5</span>. + <span class="dv">32</span>
        <span class="kw">raise</span> <span class="ot">AttributeError</span>(name)
    <span class="kw">def</span> <span class="ot">__setattr__</span>(<span class="ot">self</span>, name, value):
        <span class="kw">if</span> name == <span class="st">&quot;fahrenheit&quot;</span>:
            <span class="ot">self</span>.write_attr(<span class="st">&quot;celsius&quot;</span>, (value - <span class="dv">32</span>) * <span class="dv">5</span>. / <span class="dv">9</span>.)
        <span class="kw">else</span>:
            <span class="co"># call the base implementation</span>
            OBJECT.read_attr(<span class="st">&quot;__setattr__&quot;</span>)(<span class="ot">self</span>, name, value)

    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT,
              fields={<span class="st">&quot;__getattr__&quot;</span>: <span class="ot">__getattr__</span>, <span class="st">&quot;__setattr__&quot;</span>: <span class="ot">__setattr__</span>},
              metaclass=TYPE)
    obj = Instance(A)
    obj.write_attr(<span class="st">&quot;celsius&quot;</span>, <span class="dv">30</span>)
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;fahrenheit&quot;</span>) == <span class="dv">86</span> <span class="co"># test __getattr__</span>
    obj.write_attr(<span class="st">&quot;celsius&quot;</span>, <span class="dv">40</span>)
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;fahrenheit&quot;</span>) == <span class="dv">104</span>
    obj.write_attr(<span class="st">&quot;fahrenheit&quot;</span>, <span class="dv">86</span>) <span class="co"># test __setattr__</span>
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;celsius&quot;</span>) == <span class="dv">30</span>
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;fahrenheit&quot;</span>) == <span class="dv">86</span></code></pre>

<p>To pass these tests, the <code>Base.read_attr</code> and <code>Base.write_attr</code> methods need to be changed:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Base(<span class="dt">object</span>):
    ...

    <span class="kw">def</span> read_attr(<span class="ot">self</span>, fieldname):
        <span class="co">&quot;&quot;&quot; read field &#39;fieldname&#39; out of the object &quot;&quot;&quot;</span>
        result = <span class="ot">self</span>._read_dict(fieldname)
        <span class="kw">if</span> result is not MISSING:
            <span class="kw">return</span> result
        result = <span class="ot">self</span>.cls._read_from_class(fieldname)
        <span class="kw">if</span> _is_bindable(result):
            <span class="kw">return</span> _make_boundmethod(result, <span class="ot">self</span>)
        <span class="kw">if</span> result is not MISSING:
            <span class="kw">return</span> result
        meth = <span class="ot">self</span>.cls._read_from_class(<span class="st">&quot;__getattr__&quot;</span>)
        <span class="kw">if</span> meth is not MISSING:
            <span class="kw">return</span> meth(<span class="ot">self</span>, fieldname)
        <span class="kw">raise</span> <span class="ot">AttributeError</span>(fieldname)

    <span class="kw">def</span> write_attr(<span class="ot">self</span>, fieldname, value):
        <span class="co">&quot;&quot;&quot; write field &#39;fieldname&#39; into the object &quot;&quot;&quot;</span>
        meth = <span class="ot">self</span>.cls._read_from_class(<span class="st">&quot;__setattr__&quot;</span>)
        <span class="kw">return</span> meth(<span class="ot">self</span>, fieldname, value)</code></pre>

<p>The procedure for reading an attribute is changed to call the <code>__getattr__</code> method with the fieldname as an argument, if the method exists, instead of raising an error. Note that <code>__getattr__</code> (and indeed all special methods in Python) is looked up on the class only, instead of recursively calling <code>self.read_attr(&quot;__getattr__&quot;)</code>. That is because the latter would lead to an infinite recursion of <code>read_attr</code> if <code>__getattr__</code> were not defined on the object.</p>

<p>Writing of attributes is fully deferred to the <code>__setattr__</code> method. To make this work, <code>OBJECT</code> needs to have a <code>__setattr__</code> method that calls the default behaviour, as follows:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> OBJECT__setattr__(<span class="ot">self</span>, fieldname, value):
    <span class="ot">self</span>._write_dict(fieldname, value)
OBJECT = Class(<span class="st">&quot;object&quot;</span>, <span class="ot">None</span>, {<span class="st">&quot;__setattr__&quot;</span>: OBJECT__setattr__}, <span class="ot">None</span>)</code></pre>

<p>The behaviour of <code>OBJECT__setattr__</code> is like the previous behaviour of <code>write_attr</code>. With these modifications, the new test passes.</p>

<h3 id="descriptor-protocol">Descriptor Protocol</h3>

<p>The above test to provide automatic conversion between different temperature scales worked but was annoying to write, as the attribute name needed to be checked explicitly in the <code>__getattr__</code> and <code>__setattr__</code> methods. To get around this, the <em>descriptor protocol</em> was introduced in Python.</p>

<p>While <code>__getattr__</code> and <code>__setattr__</code> are called on the object the attribute is being read from, the descriptor protocol calls a special method on the <em>result</em> of getting an attribute from an object. It can be seen as the generalization of binding a method to an object – and indeed, binding a method to an object is done using the descriptor protocol. In addition to bound methods, the most important use case for the descriptor protocol in Python is the implementation of <code>staticmethod</code>, <code>classmethod</code> and <code>property</code>.</p>

<p>In this subsection we will introduce the subset of the descriptor protocol which deals with binding objects. This is done using the special method <code>__get__</code>, and is best explained with an example test:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_get():
    <span class="co"># Python code</span>
    <span class="kw">class</span> FahrenheitGetter(<span class="dt">object</span>):
        <span class="kw">def</span> <span class="ot">__get__</span>(<span class="ot">self</span>, inst, cls):
            <span class="kw">return</span> inst.celsius * <span class="dv">9</span>. / <span class="dv">5</span>. + <span class="dv">32</span>

    <span class="kw">class</span> A(<span class="dt">object</span>):
        fahrenheit = FahrenheitGetter()
    obj = A()
    obj.celsius = <span class="dv">30</span>
    <span class="kw">assert</span> obj.fahrenheit == <span class="dv">86</span>

    <span class="co"># Object model code</span>
    <span class="kw">class</span> FahrenheitGetter(<span class="dt">object</span>):
        <span class="kw">def</span> <span class="ot">__get__</span>(<span class="ot">self</span>, inst, cls):
            <span class="kw">return</span> inst.read_attr(<span class="st">&quot;celsius&quot;</span>) * <span class="dv">9</span>. / <span class="dv">5</span>. + <span class="dv">32</span>

    A = Class(name=<span class="st">&quot;A&quot;</span>, base_class=OBJECT,
              fields={<span class="st">&quot;fahrenheit&quot;</span>: FahrenheitGetter()},
              metaclass=TYPE)
    obj = Instance(A)
    obj.write_attr(<span class="st">&quot;celsius&quot;</span>, <span class="dv">30</span>)
    <span class="kw">assert</span> obj.read_attr(<span class="st">&quot;fahrenheit&quot;</span>) == <span class="dv">86</span></code></pre>

<p>The <code>__get__</code> method is called on the <code>FahrenheitGetter</code> instance after that has been looked up in the class of <code>obj</code>. The arguments to <code>__get__</code> are the instance where the lookup was done<a href="#fn5" class="footnoteRef" id="fnref5"><sup>5</sup></a>.</p>

<p>Implementing this behaviour is easy. We simply need to change <code>_is_bindable</code> and <code>_make_boundmethod</code>:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> _is_bindable(meth):
    <span class="kw">return</span> <span class="dt">hasattr</span>(meth, <span class="st">&quot;__get__&quot;</span>)

<span class="kw">def</span> _make_boundmethod(meth, <span class="ot">self</span>):
    <span class="kw">return</span> meth.<span class="ot">__get__</span>(<span class="ot">self</span>, <span class="ot">None</span>)</code></pre>

<p>This makes the test pass. The previous tests about bound methods also still pass, as Python's functions have a <code>__get__</code> method that returns a bound method object.</p>

<p>In practice, the descriptor protocol is quite a lot more complex. It also supports <code>__set__</code> to override what setting an attribute means on a per-attribute basis. Also, the current implementation is cutting a few corners. Note that <code>_make_boundmethod</code> calls the method <code>__get__</code> on the implementation level, instead of using <code>meth.read_attr(&quot;__get__&quot;)</code>. This is necessary since our object model borrows functions and thus methods from Python, instead of having a representation for them that uses the object model. A more complete object model would have to solve this problem.</p>

<h2 id="instance-optimization">Instance Optimization</h2>

<p>While the first three variants of the object model were concerned with behavioural variation, in this last section we will look at an optimization without any behavioural impact. This optimization is called <em>maps</em> and was pioneered in the VM for the Self programming language<a href="#fn6" class="footnoteRef" id="fnref6"><sup>6</sup></a>. It is still one of the most important object model optimizations: it's used in PyPy and all modern JavaScript VMs, such as V8 (where the optimization is called <em>hidden classes</em>).</p>

<p>The optimization starts from the following observation: In the object model as implemented so far all instances use a full dictionary to store their attributes. A dictionary is implemented using a hash map, which takes a lot of memory. In addition, the dictionaries of instances of the same class typically have the same keys as well. For example, given a class <code>Point</code>, the keys of all its instances' dictionaries are likely <code>&quot;x&quot;</code> and <code>&quot;y&quot;</code>.</p>

<p>The maps optimization exploits this fact. It effectively splits up the dictionary of every instance into two parts. A part storing the keys (the map) that can be shared between all instances with the same set of attribute names. The instance then only stores a reference to the shared map and the values of the attributes in a list (which is a lot more compact in memory than a dictionary). The map stores a mapping from attribute names to indexes into that list.</p>

<p>A simple test of that behaviour looks like this:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> test_maps():
    <span class="co"># white box test inspecting the implementation</span>
    Point = Class(name=<span class="st">&quot;Point&quot;</span>, base_class=OBJECT, fields={}, metaclass=TYPE)
    p1 = Instance(Point)
    p1.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">1</span>)
    p1.write_attr(<span class="st">&quot;y&quot;</span>, <span class="dv">2</span>)
    <span class="kw">assert</span> p1.storage == [<span class="dv">1</span>, <span class="dv">2</span>]
    <span class="kw">assert</span> p1.<span class="dt">map</span>.attrs == {<span class="st">&quot;x&quot;</span>: <span class="dv">0</span>, <span class="st">&quot;y&quot;</span>: <span class="dv">1</span>}

    p2 = Instance(Point)
    p2.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">5</span>)
    p2.write_attr(<span class="st">&quot;y&quot;</span>, <span class="dv">6</span>)
    <span class="kw">assert</span> p1.<span class="dt">map</span> is p2.<span class="dt">map</span>
    <span class="kw">assert</span> p2.storage == [<span class="dv">5</span>, <span class="dv">6</span>]

    p1.write_attr(<span class="st">&quot;x&quot;</span>, -<span class="dv">1</span>)
    p1.write_attr(<span class="st">&quot;y&quot;</span>, -<span class="dv">2</span>)
    <span class="kw">assert</span> p1.<span class="dt">map</span> is p2.<span class="dt">map</span>
    <span class="kw">assert</span> p1.storage == [-<span class="dv">1</span>, -<span class="dv">2</span>]

    p3 = Instance(Point)
    p3.write_attr(<span class="st">&quot;x&quot;</span>, <span class="dv">100</span>)
    p3.write_attr(<span class="st">&quot;z&quot;</span>, -<span class="dv">343</span>)
    <span class="kw">assert</span> p3.<span class="dt">map</span> is not p1.<span class="dt">map</span>
    <span class="kw">assert</span> p3.<span class="dt">map</span>.attrs == {<span class="st">&quot;x&quot;</span>: <span class="dv">0</span>, <span class="st">&quot;z&quot;</span>: <span class="dv">1</span>}</code></pre>

<p>Note that this is a different flavour of test than the ones we've written before. All previous tests just tested the behaviour of the classes via the exposed interfaces. This test instead checks the implementation details of the <code>Instance</code> class by reading internal attributes and comparing them to predefined values. Therefore this test can be called a <em>white-box</em> test.</p>

<p>The <code>attrs</code> attribute of the map of <code>p1</code> describes the layout of the instance as having two attributes <code>&quot;x&quot;</code> and <code>&quot;y&quot;</code> which are stored at position 0 and 1 of the <code>storage</code> of <code>p1</code>. Making a second instance <code>p2</code> and adding to it the same attributes in the same order will make it end up with the same map. If, on the other hand, a different attribute is added, the map can of course not be shared.</p>

<p>The <code>Map</code> class looks like this:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Map(<span class="dt">object</span>):
    <span class="kw">def</span> <span class="ot">__init__</span>(<span class="ot">self</span>, attrs):
        <span class="ot">self</span>.attrs = attrs
        <span class="ot">self</span>.next_maps = {}

    <span class="kw">def</span> get_index(<span class="ot">self</span>, fieldname):
        <span class="kw">return</span> <span class="ot">self</span>.attrs.get(fieldname, -<span class="dv">1</span>)

    <span class="kw">def</span> next_map(<span class="ot">self</span>, fieldname):
        <span class="kw">assert</span> fieldname not in <span class="ot">self</span>.attrs
        <span class="kw">if</span> fieldname in <span class="ot">self</span>.next_maps:
            <span class="kw">return</span> <span class="ot">self</span>.next_maps[fieldname]
        attrs = <span class="ot">self</span>.attrs.copy()
        attrs[fieldname] = <span class="dt">len</span>(attrs)
        result = <span class="ot">self</span>.next_maps[fieldname] = Map(attrs)
        <span class="kw">return</span> result

EMPTY_MAP = Map({})</code></pre>

<p>Maps have two methods, <code>get_index</code> and <code>next_map</code>. The former is used to find the index of an attribute name in the object's storage. The latter is used when a new attribute is added to an object. In that case the object needs to use a different map, which <code>next_map</code> computes. The method uses the <code>next_maps</code> dictionary to cache already created maps. That way, objects that have the same layout also end up using the same <code>Map</code> object.</p>

<div class="center figure">
<a name="figure-14.2"></a><img src="objmodel-images/maptransition.png" alt="Figure 14.2 - Map transitions" title="Figure 14.2 - Map transitions" />
</div>

<p class="center figcaption">
<small>Figure 14.2 - Map transitions</small>
</p>

<p>The <code>Instance</code> implementation that uses maps looks like this:</p>

<pre class="sourceCode python"><code class="sourceCode python"><span class="kw">class</span> Instance(Base):
    <span class="co">&quot;&quot;&quot;Instance of a user-defined class. &quot;&quot;&quot;</span>

    <span class="kw">def</span> <span class="ot">__init__</span>(<span class="ot">self</span>, cls):
        <span class="kw">assert</span> <span class="dt">isinstance</span>(cls, Class)
        Base.<span class="ot">__init__</span>(<span class="ot">self</span>, cls, <span class="ot">None</span>)
        <span class="ot">self</span>.<span class="dt">map</span> = EMPTY_MAP
        <span class="ot">self</span>.storage = []

    <span class="kw">def</span> _read_dict(<span class="ot">self</span>, fieldname):
        index = <span class="ot">self</span>.<span class="dt">map</span>.get_index(fieldname)
        <span class="kw">if</span> index == -<span class="dv">1</span>:
            <span class="kw">return</span> MISSING
        <span class="kw">return</span> <span class="ot">self</span>.storage[index]

    <span class="kw">def</span> _write_dict(<span class="ot">self</span>, fieldname, value):
        index = <span class="ot">self</span>.<span class="dt">map</span>.get_index(fieldname)
        <span class="kw">if</span> index != -<span class="dv">1</span>:
            <span class="ot">self</span>.storage[index] = value
        <span class="kw">else</span>:
            new_map = <span class="ot">self</span>.<span class="dt">map</span>.next_map(fieldname)
            <span class="ot">self</span>.storage.append(value)
            <span class="ot">self</span>.<span class="dt">map</span> = new_map</code></pre>

<p>The class now passes <code>None</code> as the fields dictionary to <code>Base</code>, as <code>Instance</code> will store the content of the dictionary in another way. Therefore it needs to override the <code>_read_dict</code> and <code>_write_dict</code> methods. In a real implementation, we would refactor the <code>Base</code> class so that it is no longer responsible for storing the fields dictionary, but for now having instances store <code>None</code> there is good enough.</p>

<p>A newly created instance starts out using the <code>EMPTY_MAP</code>, which has no attributes, and empty storage. To implement <code>_read_dict</code>, the instance's map is asked for the index of the attribute name. Then the corresponding entry of the storage list is returned.</p>

<p>Writing into the fields dictionary has two cases. On the one hand the value of an existing attribute can be changed. This is done by simply changing the storage at the corresponding index. On the other hand, if the attribute does not exist yet, a <em>map transition</em> (<a href="#figure-14.2">Figure 14.2</a>) is needed using the <code>next_map</code> method. The value of the new attribute is appended to the storage list.</p>

<p>What does this optimization achieve? It optimizes use of memory in the common case where there are many instances with the same layout. It is not a universal optimization: code that creates instances with wildly different sets of attributes will have a larger memory footprint than if we just use dictionaries.</p>

<p>This is a common problem when optimizing dynamic languages. It is often not possible to find optimizations that are faster or use less memory in all cases. In practice, the optimizations chosen apply to how the language is <em>typically</em> used, while potentially making behaviour worse for programs that use extremely dynamic features.</p>

<p>Another interesting aspect of maps is that, while here they only optimize for memory use, in actual VMs that use a just-in-time (JIT) compiler they also improve the performance of the program. To achieve that, the JIT uses the maps to compile attribute lookups to a lookup in the objects' storage at a fixed offset, getting rid of all dictionary lookups completely<a href="#fn7" class="footnoteRef" id="fnref7"><sup>7</sup></a>.</p>

<h2 id="potential-extensions">Potential Extensions</h2>

<p>It is easy to extend our object model and experiment with various language design choices. Here are some possibilities:</p>

<ul>
<li><p>The easiest thing to do is to add further special methods. Some easy and interesting ones to add are <code>__init__</code>, <code>__getattribute__</code>, <code>__set__</code>.</p></li>
<li><p>The model can be very easily extended to support multiple inheritance. To do this, every class would get a list of base classes. Then the <code>Class.method_resolution_order</code> method would need to be changed to support looking up methods. A simple method resolution order could be computed using a depth-first search with removal of duplicates. A more complicated but better one is the <a href="https://www.python.org/download/releases/2.3/mro/">C3 algorithm</a>, which adds better handling in the base of diamond-shaped multiple inheritance hierarchies and rejects insensible inheritance patterns.</p></li>
<li><p>A more radical change is to switch to a prototype model, which involves the removal of the distinction between classes and instances.</p></li>
</ul>

<h2 id="conclusions">Conclusions</h2>

<p>Some of the core aspects of the design of an object-oriented programming language are the details of its object model. Writing small object model prototypes is an easy and fun way to understand the inner workings of existing languages better and to get insights into the design space of object-oriented languages. Playing with object models is a good way to experiment with different language design ideas without having to worry about the more boring parts of language implementation, such as parsing and executing code.</p>

<p>Such object models can also be useful in practice, not just as vehicles for experimentation. They can be embedded in and used from other languages. Examples of this approach are common: the GObject object model, written in C, that's used in GLib and other Gnome libraries; or the various class system implementations in JavaScript.</p>

<div class="footnotes">
<ol>
<li id="fn1"><p>P. Cointe, “Metaclasses are first class: The ObjVlisp Model,” SIGPLAN Not, vol. 22, no. 12, pp. 156–162, 1987.<a href="#fnref1">↩</a></p></li>
<li id="fn2"><p>It seems that the attribute-based model is conceptually more complex, because it needs both method lookup and call. In practice, calling something is defined by looking up and calling a special attribute <code>__call__</code>, so conceptual simplicity is regained. This won't be implemented in this chapter, however.)<a href="#fnref2">↩</a></p></li>
<li id="fn3"><p>G. Kiczales, J. des Rivieres, and D. G. Bobrow, The Art of the Metaobject Protocol. Cambridge, Mass: The MIT Press, 1991.<a href="#fnref3">↩</a></p></li>
<li id="fn4"><p>A. Goldberg, Smalltalk-80: The Language and its Implementation. Addison-Wesley, 1983, page 61.<a href="#fnref4">↩</a></p></li>
<li id="fn5"><p>In Python the second argument is the class where the attribute was found, though we will ignore that here.<a href="#fnref5">↩</a></p></li>
<li id="fn6"><p>C. Chambers, D. Ungar, and E. Lee, “An efficient implementation of SELF, a dynamically-typed object-oriented language based on prototypes,” in OOPSLA, 1989, vol. 24.<a href="#fnref6">↩</a></p></li>
<li id="fn7"><p>How that works is beyond the scope of this chapter. I tried to give a reasonably readable account of it in a paper I wrote a few years ago. It uses an object model that is basically a variant of the one in this chapter: C. F. Bolz, A. Cuni, M. Fijałkowski, M. Leuschel, S. Pedroni, and A. Rigo, “Runtime feedback in a meta-tracing JIT for efficient dynamic languages,” in Proceedings of the 6th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems, New York, NY, USA, 2011, pp. 9:1–9:8.<a href="#fnref7">↩</a></p></li>
</ol>
</div>
  </body>
</html>
